#include "string_array.h"

using namespace std;

myStr::myStr(const char* ch) {
    next = new int; nextVal = new int;
    int i = 0;
    while (ch[i] != '\0')
        ch[i++];
    data = new char[i];
    length = i;
    while (i--)data[i] = ch[i];
    //data[i] = '\0';
}

//销毁字符串
myStr::~myStr() {
    length = 0;
    delete data; data = NULL;
    delete next; next = NULL;
    delete nextVal; nextVal = NULL;
}
void myStr::kmp_next() {
    next = new int[length];
    next[0] = 0;
    if (length > 1)
        next[1] = 1;
        int j=1;
        int k=0;
    for (int i = 2; i < this->length; i++) {
        int j = -1;
        int p;
        for (p = i - 1; p >= 1; p--) 
		{
            int g = 0;
            for (int w = 0; w < p; w++) 
			{
                if (data[w] == data[i - p + w])g++;
            }
            if (g == p)break;
        }
        next[i] = p + 1;
    }
}
void myStr::kmp_nextVal() 
{
    nextVal = new int[length];
    nextVal[0] = 0;
    for (int i = 1; i < this->length; i++) {
        nextVal[i] = 0;
        char x, y;
        x = data[i];
        y = data[next[i] - 1];
        if (x != y)nextVal[i] = next[i];
        else if(x==y)nextVal[i] = nextVal[next[i]-1];
    }
}

//串的替换
bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V) {
    int i = simpleMatch(S, T);
    if (i == -1||i<start)return 0;
    else i--;
    int j = i + 1, vl = V.length, sl = S.length;
    char* ch = S.data;
    S.length = S.length - T.length + V.length;
    S.data = new char[S.length];
    for (j = 0; j < i; j++)
        S.data[j] = ch[j];
    for (j = 0; j < vl; j++)
        S.data[i + j] = V.data[j];
    for (j = j + i; j < sl; j++)
        S.data[j] = ch[j+T.length-V.length];
    return 1;
}
//查找子串
int simpleMatch(const myStr& S, const myStr& T) {
    int i, num;
    for (i = 0; i < S.length; i++)
    {
        num = 0;
        for (int j = 0; j < T.length; j++)
        {
            if (S.data[i + j] == T.data[j])num++;
            else break;
        }
        if (num == T.length)break;
    }
    if (i == S.length)return -1;
    else return i + 1;
}
//KPM查找子串
int kmpMatch(const myStr& S, const myStr& T) {
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length) {
        if (j == 0 || S.data[i - 1] == T.data[j - 1]) { i++; j++; }
        else j = T.next[j - 1];
    }
    if (j >T.length)return i - T.length;
    else return -1;
}
//输出字符串
void myStr::print() {
    for (int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}
//输出next数组
void myStr::printNext() {
    for (int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}
//输出nextVal数组
void myStr::printNextVal() {
    for (int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}
//初始化矩阵
myMatrix::myMatrix() {
    rowNum = 0; colNum = 0; nodeNum = 0;
    nodeList = new matrixNode;
}
myMatrix::myMatrix(const int& rNum, const int& cNum, const int& nNum, const int* i)
{
    nodeNum = nNum;
    nodeList = new matrixNode[nodeNum];
    int j = 0;
    int k = 0;
    while (j < nodeNum) {
        nodeList[j].row = i[k];
        k++;
        nodeList[j].col = i[k];
        k++;
        nodeList[j].value = i[k];
        k++;
        j++;
    }
    for (int i = 2; i <= nNum; i++) {
        for (int j = 0; j <= nNum - i; j++) {
            if (nodeList[j].row > nodeList[j + 1].row) {//如果说前面那个元素的行大的话就和后面那个元素交换行、列、值
                int temp_row = nodeList[j].row;
                int temp_col = nodeList[j].col;
                int temp_value = nodeList[j].value;
                nodeList[j].row = nodeList[j + 1].row;//交换行
                nodeList[j + 1].row = temp_row;
                nodeList[j].col = nodeList[j + 1].col;//交换列
                nodeList[j + 1].col = temp_col;
                nodeList[j].value = nodeList[j + 1].value;//交换值
                nodeList[j + 1].value = temp_value;
            }
            if (nodeList[j].row == nodeList[j + 1].row && nodeList[j].col > nodeList[j + 1].col) {
                int temp_row = nodeList[j].row;
                int temp_col = nodeList[j].col;
                int temp_value = nodeList[j].value;
                nodeList[j].row = nodeList[j + 1].row;//交换行
                nodeList[j + 1].row = temp_row;
                nodeList[j].col = nodeList[j + 1].col;//交换列
                nodeList[j + 1].col = temp_col;
                nodeList[j].value = nodeList[j + 1].value;//交换值
                nodeList[j + 1].value = temp_value;
            }
            if (nodeList[j].row == nodeList[j + 1].row && nodeList[j].col == nodeList[j + 1].col && nodeList[j].value > nodeList[j + 1].value) {
                int temp_row = nodeList[j].row;
                int temp_col = nodeList[j].col;
                int temp_value = nodeList[j].value;
                nodeList[j].row = nodeList[j + 1].row;//交换行
                nodeList[j + 1].row = temp_row;
                nodeList[j].col = nodeList[j + 1].col;//交换列
                nodeList[j + 1].col = temp_col;
                nodeList[j].value = nodeList[j + 1].value;//交换值
                nodeList[j + 1].value = temp_value;
            }
        }
    }
    rowNum = rNum;
    colNum = cNum;
}

//销毁矩阵
myMatrix::~myMatrix() {
    rowNum = 0; colNum = 0; nodeNum = 0;
    delete nodeList; nodeList = NULL;
}
//倒置矩阵
void myMatrix::FastTransposeSMatrix(myMatrix& T) {
    T.rowNum = colNum; T.colNum = rowNum; T.nodeNum = nodeNum;
    T.nodeList = new matrixNode[nodeNum];
    if (nodeNum) {
        int i = 0, col, p;
        for ( col = 1; col < colNum; col++)
            for ( p = 0; p < nodeNum; p++)
                if (nodeList[p].col==col)
                {
                    T.nodeList[i].col = nodeList[i].row;
                    T.nodeList[i].row = nodeList[i].col;
                    T.nodeList[i].value = nodeList[i].value;
                    i++;
                }
    }
}
//打印矩阵
void myMatrix::printMatrix() {
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for (int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}
